//
// Created by 梦小星 on 2021/10/25.
// @author 梦小星 https://mengxiaoxing.top
// @mail mengxingcn@aliyun.com
//
#include <iostream>
#include "SqList.h"

using namespace std;
/*
 * 递增有序的顺序表中快速查找元素x，若找到将其与后继元素互换，若找不到将元素x插入表中并保证表依旧有序
 * 算法思想；有序顺序表快速查找用二分查找，
 *
 * */
/*
 * 使用二分查找
 * 参数 x 要查找的元素
 * 是否查询成功，若成功返回元素的位置,如果失败返回右指针的位置
 * */
bool search(SqList list,int x,int &pos){
    int left=0,right=list.length-1;
    while (left<=right){
        int mid=(right+left)/2;
        if (list.data[mid]==x){
            cout << left << "," <<right <<"," << mid << endl;
            pos=mid;
            return true;
        } else if(list.data[mid]<x){
            left=mid+1;
        } else if(list.data[mid]>x){
            right=mid-1;
        }
    }
    cout << left << "," <<right  << endl;
    pos=right;
    return false;
}
/*
 * 插入元素
 * */
void insert(SqList &list,int pos,int data){
    for (int i = list.length-1; i > pos; --i) {
        list.data[i+1]=list.data[i];
    }
    list.data[pos+1]=data;
    list.length++;
}
/*
 * 交换元素
 * */
void exchange(SqList &list,int indexX){
    int tmp=list.data[indexX];
    list.data[indexX]=list.data[indexX+1];
    list.data[indexX+1]=tmp;
}

/*
 * 方法二
 * */
void searchAndExchange(SqList &list,int x){
    int left=0,right=list.length-1,mid=0;
//    二分查找
    while (left<=right){
         mid=(right+left)/2;
        if (list.data[mid]==x){
            break;
        }else if(list.data[mid]<x){
            left=mid+1;
        } else if(list.data[mid]>x){
            right=mid-1;
        }
    }
//    查找成功且不是表尾
    if (list.data[mid]==x&&mid!=right){
        int tmp=list.data[mid];
        list.data[mid]=list.data[mid+1];
        list.data[mid+1]=tmp;
    }
//    查找失败
    if (left>right){
        for (int i = list.length-1; i > right; --i) {
            list.data[i+1]=list.data[i];
        }
        list.data[right+1]=x;
        list.length++;
    }
}
int main(){
    SqList list;
    initList(list);
    for (int i = 0; i < 10; ++i) {
        cout <<i+1<<',';
        listInsert(list,i+1,i*2);
    }
    cout <<endl;
    printList(list);
    int pos=0,x=18;
    if (!search(list,x,pos)){
//        没有找到则插入
        insert(list,pos,x);
    } else if (pos!=list.length-1){
//        找到且不是最后一个则交换位置
        exchange(list,pos);
    }
    printList(list);
}
